package cn.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Code438 {
    public static void main(String[] args) {
        List<Integer> anagrams = findAnagramsPlus("cbaebabacd", "abc");
        System.out.println(anagrams);
    }

    public static List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> map2 = new HashMap<>();
        for (int j=0; j<p.length(); j++){
            clean(map2, p, j);
        }

        int length = p.length();
        Map<Character, Integer> map1 = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        A: for(int i=0; i<=s.length()-p.length(); i++){
            map1.clear();
            String substring = s.substring(i, length+i);
            for(int j=0; j<length; j++){
                clean(map1, substring, j);
            }
            for(int j=0; j<length; j++){
                char c1 = substring.charAt(j);
                Integer integer1 = map1.get(c1);
                Integer integer2 = map2.get(c1);
                if(!integer1.equals(integer2)){
                    continue A;
                }
            }
            result.add(i);
        }
        return result;
    }

    private static void clean(Map<Character, Integer> map1, String substring, int j) {
        char c1 = substring.charAt(j);
        Integer integer1 = map1.get(c1);
        if(integer1 == null){
            map1.put(c1, 1);
        }else{
            int i1 = integer1 + 1;
            map1.put(c1, i1);
        }
    }

    public static List<Integer> findAnagramsPlus(String s, String p) {
        List<Integer> result = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        for (int i=0; i<p.length(); i++){
            char c = p.charAt(i);
            map.merge(c, 1, Integer::sum);
        }
        int count = 0;
        int j = 0;
        for (int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            Integer integer = map.get(c);
            if(integer != null){
                Integer in = map.get(c);
                if(in > 0){
                    count++;
                    map.put(c, in - 1);
                }else{
                    char d = s.charAt(j);
                    if (c != d) {
                        while (c != d) {
                            Integer num = map.get(d);
                            map.put(d, num + 1);
                            j++;
                            d = s.charAt(j);
                            count--;
                        }
                    }
                    j++;
                }
            } else {
                char d = s.charAt(j);
                while (j != i){
                    Integer in = map.get(d);
                    if(in != null){
                        map.put(d, in+1);
                        count--;
                    }
                    j++;
                    d = s.charAt(j);
                }
                j++;
            }
            if(count == p.length()){
                int num = i + 1 - p.length();
                result.add(num);
            }
        }
        return result;
    }
}
